Leetcode 基础题

发表于 | 分类于 | | 阅读次数

毕业找工作的时候，拼了老命了复习算法，认为科班出身，学好算法才是自己的优势，同时，像谷歌，微软等比较top的公司，非常注重算法的考察，因此，一门心思的去学。但后来才发现，并没有什么用。想进谷歌，微软，靠的是智商，天生不可逆转的东西，后天很难补。过度专研算法难题，并没有用，其实面试，算法还是考察的比较基础。结果找工作果断悲剧，算法真的没有面的特别难，相反，知道我不是ACM出生，算法考察的还是很基础，更多的集中在计算机的理论知识。校招时，不但BAT全被据，二线互联网才有一个携程和eBay，工资都不太理想，再加上已经草签了HW，毁约有拿不到户口的风险，因此找工作就草草结束了。回想起来，确实浪费了太多无用的时间在算法上，也没有很精通，返回耽误了很多基础知识的准备，两头的不靠岸。世界没有后悔药吃，不可能回到毕业季重新参加校招了，职业生涯也变得很迷茫。。。

毕业半年参加社招，参加了新美大的社招面试，在完全没有准备算法的情况下，事实上面试时一道算法也没问，全被准备Java相关理论知识，居然顺利拿到offer，回想起来多讽刺，当初几乎90%的时间都花在算法上，却完全没用武之地，如果回到当时，好好像现在准备项目，Java知识，获取校招时，至少能拿个BAT的offer

001_Medium: Two Sum. hashMap应用

005_Mesium:最长回文。简单的二维DP

007_Easy: 反转整数，注意负号和Integer的溢

1
2
3
4
while(x != 0){
re = (re*10 + x%10);
x /= 10;
}

012_Medium:Integer to Roman. 循环遍历，比较基础，理解题意很重要

015_Medium: 3Sum.给定数组，找到3个数的和等于0. 排序，固定一个数，二分查找搜索另外两个数

017_Medium:Letter Combinations of a Phone Number. 9宫格键盘，表示字母的组合。典型的dfs

020_Easy: Valid Parentheses. 判断括号组合的合法性。栈的典型应用

026_Easy: Remove Duplicates from Sorted Array. 移除已排序数组中的重复元素。双指针典型应用

034_Medium: Search for a Range. 给定一个已经排序的数组和一个数字，找到数组中这个数出现的下标范围。二分查找典型应用，当查找到时，向左还是向右的处理方法。

039_Medium: Combination Sum. 给定一个数组和一个target数字，找到数组中所有子数组可能的组合，使得子数组的和等于target。 典型的回溯法，和求全排列一样，暴力求解。

044_Hard: Wildcard Matching.两个字符串匹配，？匹配任意一个字符，匹配0个或多个字符。典型的动态规划，Match[i+1][j+1]表示s[0…i]和p[0…j]是否匹配，重点考虑当p[j] = ‘‘时，分两种情况，1：p[j]一个字符都不匹配-> isMathch[i+1][j];2:p[j]匹配至少一个字符->isMathch[i][j+1]。思路感觉很巧妙

046_Medium_Permutations：生成数组全排列。典型的回溯法

048_Medium: Rotate Image. 顺时针旋转nn的矩阵，要求in-place操作。*先转置，在左右或者上下倒转

053_Medium: Maximum Subarray. 求最大连续字数组和。典型的一维动态规划